The present invention relates generally to network management, and more specifically to scheduling messages for Asynchronous Transfer Mode (ATM) networks.
As ATM technology becomes increasingly popular for Broadband ISDN, it must be able to support traffic having different Quality of Service (QoS) requirements, and this requires priority control in scheduling the transmission of cells in ATM messages. Thus, optimal use of network resources without sacrificing QoS requires that the ATM switches use proper scheduling disciplines to mediate the departure of ATM cells and discard cells on a priority basis. These priority-based scheduling disciplines fall into one of three main categories: delay-based, loss-based, or delay-and-loss-based.
In the delay-based category, the Head-Of-Line (HOL) discipline offers stringent delay guarantees for real-time cells but at the expense of increased buffering delays for non-real-time cells. Several disciplines attempt to control the performance tradeoff between real-time and non-real-time cells. The Minimum Laxity Threshold (MLT) and Earliest Due Date (EDD) disciplines manage the performance trade-off from the time perspective. The MLT discipline grants higher priority to real-time cells only when the minimum laxity (defined as the amount of time until the earliest deadline of a queued real-time cell expires) has not exceeded threshold L. The EDD discipline allows a real-time cell to precede non-real-time cells arriving not prior to slot time D.
The Queue Length Threshold (QLT) and Threshold Based Priority (TBP) disciplines manage the performance trade-off from a space perspective. The QLT discipline concedes ERON, precedence to real-time cells only when the number of queued non-real-time cells does not exceed a threshold T. The TBP discipline, on the other hand, allows real-time cells to take precedence when the number of queued real-time cells exceeds a threshold L.
These delay-based disciplines retain adequate QoS for real-time cells while offering the best possible service to non-real-time cells. The success of these disciplines hinges on the effective determination of the thresholds L, D, or T.
In the loss-based category, the Complete Buffer Partitioning discipline divides the queue into two regions dedicated to loss-sensitive and loss-insensitive cells, respectively. This discipline is prone to queue wastage, however, because no queue sharing takes place.
The Nested Threshold Cell Discarding (NTCD) (or partial buffer sharing) discipline allows loss-insensitive cells to share the queue until the queue occupancy reaches a threshold T. The NTCD discipline results in poor space utilization, however, when the loss-sensitive traffic load is low.
To alleviate the problem, the Push-Out buffer sharing (PO) discipline allows newly-arriving loss-sensitive cells to push out loss-insensitive cells if the queue is full. However, the PO discipline does not offer any adjustment of the Cell Loss Ratio (CLR) for any traffic class.
In a Threshold Push-Out (TPO) discipline, a loss-sensitive cell observing a full queue upon arrival can push out a loss-insensitive cell if the number of loss-insensitive cells exceeds a threshold T. In a PowPush-Out(PowPO) discipline, a newly-arriving loss-sensitive cell observing a fall queue can push out a loss-insensitive cell with probability Pow.
To consider both delay and loss requirements in the delay-and-loss-based category, the Nested Threshold Cell Discarding with Multiple Buffers (NTCD-MB) discipline allows real-time cells to enter one smaller queue employing NTCD and allows loss-sensitive cells to enter another larger queue. Loss-sensitive cells are served only when there is no real-time cell in the smaller-size queue. This discipline offers stringent delay and loss guarantees for real-time cells and loss-sensitive cells, respectively, but wastes space because of two independent queues.
The Head-of-Line with Push-Out (HLPO) discipline uses HOL and PO disciplines for real-time cells and loss-sensitive cells, respectively. The HLPO discipline, however, does not provide any adjustment of the Cell Delay (CD) and CLR for any traffic class.
To provide an improved scheduling discipline, a scheduling method consistent with this invention comprises: (1) determining whether a message queue is full; (2) determining whether a newly-arriving cell is a high priority cell if the message queue is full; (3) placing the newly-arriving cell into the message queue before a predetermined number of low-priority cells in the queue if the newly-arriving cell is a high-delay-priority cell and if the queue is not full; and (4) placing the newly-arriving cell into the queue in the place of a selected low-priority cell in the queue if the queue is full, the newly-arriving cell is a high-loss-priority cell, and the selected low-loss-priority cell is located beyond a predetermined location in the queue.
A message scheduler consistent with this invention comprises a message queue and a processor for controlling the entry of cells into the queue. The processor includes (1) means for determining whether the message queue is full; (2) means for determining whether a newly-arriving cell is a high priority cell if the message queue is full; (3) means for placing the newly-arriving cell into the message queue before a predetermined number of low-priority cells in the queue if the newly-arriving cell is a high-delay-priority cell and if the queue is not full; and (4) means for placing the newly-arriving cell into the queue in the place of a selected low-priority cell in the queue if the queue is full, the newly-arriving cell is a high-loss-priority cell, and the selected low-loss-priority cell is located beyond a predetermined location in the queue.
Both the foregoing general description and the following detailed description are exemplary and explanatory only and do not restrict the invention claimed. The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate some systems and methods consistent with the invention and, together with the description, explain the principles of the invention.